//环形链表 II
/*给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        ListNode* s = head;
        ListNode* q = head;
        while (q && q->next) {
            q = q->next->next;
            s = s->next;
            if (s == q)
                break;
        }
        if (s == nullptr)
            return s;
        else if (s->next == nullptr)
            return nullptr;
        ListNode* _s = head;
        while (s && _s != s) {
            _s = _s->next;
            s = s->next;
        }
        return s;
    }
};

//随机链表的复制
/*给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。

 */
 /*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, int> Map;
        vector<Node*> arr;
        Node* _head = new Node(-1);
        Node* temp = head;
        Node* _temp = _head;
        while (temp) {
            _temp->next = new Node(temp->val);
            Map[temp] = arr.size();
            temp = temp->next;
            _temp = _temp->next;
            arr.push_back(_temp);
        }
        _temp = _head->next;
        temp = head;
        while (temp) {
            _temp->random =
                temp->random == nullptr ? nullptr : arr[Map[temp->random]];
            temp = temp->next;
            _temp = _temp->next;
        }
        return _head->next;
    }
};